1. Field of the Invention
The present invention relates to an interleaving device and an interleaving method, for permuting the order of input data following predetermined addresses and outputting as output data, an encoding apparatus and an encoding method, for encoding by concatenating multiple component codes in parallel or serially via interleaving processing, and a decoding apparatus and a decoding method, for decoding generated codes by concatenating multiple component codes in parallel or serially via interleaving processing.
2. Description of the Related Art
In recent years, while study with regard to the communication field such as mobile communication or deep-space communication, and the broadcasting field such as ground wave or satellite digital broadcasting, for example, has been remarkably advanced, study has also been widely undertaken with regard to code theorem for error correction encoding and efficiency improvement of encoding.
The Shannon limit obtained by the so-called Shannon's (C. E. Shannon) communication path encoding theorem is known as the theoretical limit of code performance.
Study with regard to code theorem has been made in order to develop codes exhibiting performance approaching the Shannon limit. In recent years, the Parallel Concatenated Convolutional Codes (which will be referred to as “PCCC” hereafter) or the Serially Concatenated Convolutional Codes (which will be referred to as “SCCC” hereafter), which are referred to as so-called turbo-codes, for example, have been developed as encoding methods exhibiting the performance approaching the Shannon limit.
On the other hand, in recent years, study on decoding methods corresponding to these codes, has also been widely undertaken. Specifically, studies with regard to methods for reducing the symbol error rate by employing soft-output as decoding output of inner codes in concatenated codes or output of each repeated decoding operation in the repeated decoding method has been made, and study with regard to the decoding methods suitable thereto has been widely undertaken. For example, the BCJR algorithm which is described in “Bahl, Cocke, Jelinek and Raviv, ‘Optimal Decoding of linear codes for minimizing symbol error rate’, IEEE Trans. Inf. Theory, vol. IT-20, pp. 284-287, March, 1974” is known as a method for minimizing the symbol error rate in the event of decoding predetermined codes such as convolutional codes or the like. With the BCJR algorithm, each symbol is not output, rather, the likelihood of each symbol is output as decoding results. The above-described output is referred to as soft-output.
Details of the BCJR algorithm will be described below. Let us now consider a case wherein digital information is subjected to convolutional encoding by an encoding apparatus 201 included in a transmission device which is not shown in drawings, and the output is observed by inputting the output to a receiving device, which is not shown in drawings, via a non-storage channel 202 containing noise, and decoding the output by a decoding apparatus 203 included in the receiving device, as shown in FIG. 20.
First of all, an M number of states (transition states) indicating the state of the shift resistors included in the encoding apparatus 201 are represented by m (0, 1, . . . , M−1), and the state at the time t is represented by St. Also, making an assumption that k bits of information is input in one time slot, the input at the time t is represented by it=(it1, it2, . . . , itk), and the input system is represented by I1T=(i1, i2, . . . , iT). At this time, in the event that transition from the state m′ to the state m occurs, the information bits corresponding to the transition are represented by i(m′, m)=(i1(m′, m), i2(m′, m), . . . , ik(m′, m)). Moreover, making an assumption that n bits of code are output in one time slot, the output at the time t is represented by xt=(xt1, xt2, . . . , xtn), and the output system is represented by X1T=(x1, x2, . . . , xT). At this time, in the event that the transition from the state m′ to the state m occurs, the code bit corresponding to the transition is represented by x(m′, m)=(x1(m′, m), x2(m′, m), . . . , xn(m′, m)).
The convolutional encoding by the encoding apparatus 201 begins at the state S0=0, and ends at the state ST=0 following output of X1T. Here, the transition probability Pt(m|m′) between states is defined by the following Expression (1).
Expression (1)Pt(m|m′)=Pr{St=m|St−1=m′}  (1)
Note that the Pr{A|B} shown in the right side in the above Expression (1) represents the conditional probability that A is generated under the conditions that B is generated. The transition probability Pt(m|m′) equals the probability Pr{it=i} wherein, in the event of transition from the state m′ to the state m under the input i, the input it at the time t is i, as shown in the following Expression (2).
Expression (2)Pt(m|m′)=Pr{it=i}  (2)
X1T is input to the non-storage channel 202 containing noise, and Y1T is output therefrom. Here, making an assumption that n bits of reception values are output in one time slot, the output at the time t is represented by yt=(yt1, yt2, . . . , ytn), and is represented by Y1T=(y1, y2, . . . , yT). The transition probability of the non-storage channel 202 containing noise can be defined as shown in the following Expression (3) with regard to all the t (1≦t≦T) using the transition probability Pr {yj|xj} for each symbol.Expression (3)                               Pr          ⁢                      {                                          Y                1                t                            |                              X                1                t                                      }                          =                              ∏                          j              =              1                        t                    ⁢                                           ⁢                      Pr            ⁢                          {                                                y                  j                                |                                  x                  j                                            }                                                          (        3        )            
Here, let us define λtj as shown in the following Expression (4). This λtj shown in the following Expression (4) represents the likelihood of the input information at the time t at the point that Y1T is received, and is the soft-output which is to be obtained.Expression (4)                               λ          tj                =                              Pr            ⁢                          {                                                i                  tj                                =                                  1                  |                                      Y                    1                    T                                                              }                                            Pr            ⁢                          {                                                i                  tj                                =                                  0                  |                                      Y                    1                    T                                                              }                                                          (        4        )            
In the BCJR algorithm, the probabilities αt, βt, and γt, as shown in the following Expression (5) through (7) are defined. Here, Pr{A;B} represents the probability wherein both A and B are generated.Expression (5)                                           α            t                    ⁡                      (            m            )                          =                  Pr          ⁢                      {                                                            S                  t                                =                m                            ;                              Y                1                t                                      }                                              (        5        )            Expression (6)                                           β            t                    ⁡                      (            m            )                          =                  Pr          ⁢                      {                                                            Y                                      t                    +                    1                                    T                                |                                  S                  t                                            =              m                        }                                              (        6        )            Expression (7)                                           γ            t                    ⁡                      (                                          m                ′                            ,              m                        )                          =                  Pr          ⁢                      {                                                            S                  t                                =                m                            ;                                                                    y                    t                                    |                                      S                                          t                      -                      1                                                                      =                                  m                  ′                                                      }                                              (        7        )            
Here, details of the probabilities αt, βt, and γt, will be described using a trellis, which is a state transition diagram in the encoding apparatus 201, shown in FIG. 21. In the drawing, αt−1 corresponds to the passage probability of each state at the time t−1, which is calculated based upon reception values beginning at the encoding beginning state S0=0 in time-sequence. Also, βt corresponds to the passage probability of each state at the time t, which is calculated based upon reception values beginning at the encoding end state ST=0 in inverse time-sequence.
Moreover, γt corresponds to the receiving probability of the output at each branch wherein the transition between states occurs at the time t, which is calculated based upon the reception value at the time t and the input probability.
Using the probabilities αt, βt, and γt, the soft-output λtj can be represented as shown in the following Expression (8).Expression (8)                               λ          tj                =                                            ∑                                                                    m                    ′                                    ,                  m                                                                                            i                      j                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                        =                  1                                                                                                   ⁢                                                            α                  t                                ⁡                                  (                                      m                    ′                                    )                                            ⁢                                                γ                  t                                ⁡                                  (                                                            m                      ′                                        ,                    m                                    )                                            ⁢                                                β                  t                                ⁡                                  (                  m                  )                                                                                        ∑                                                                    m                    ′                                    ,                  m                                                                                            i                      j                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                        =                  0                                                                                                   ⁢                                                            α                  t                                ⁡                                  (                                      m                    ′                                    )                                            ⁢                                                γ                  t                                ⁡                                  (                                                            m                      ′                                        ,                    m                                    )                                            ⁢                                                β                  t                                ⁡                                  (                  m                  )                                                                                        (        8        )            
Now, the following Expression (9) holds with regard to t=1, 2, . . . , T.Expression (9)                                                         α              t                        ⁡                          (              m              )                                =                                                    ∑                                                      m                    ′                                    =                  0                                                  M                  -                  1                                            ⁢                                                                    α                                          t                      -                      1                                                        ⁡                                      (                                          m                      ′                                        )                                                  ⁢                                                      γ                    t                                    ⁡                                      (                                                                  m                        ′                                            ,                      m                                        )                                                  ⁢                                                                   ⁢                ⁢                                                                   ⁢                                                      α                    0                                    ⁡                                      (                    0                    )                                                                        =            1                          ,                                            α              0                        ⁡                          (              m              )                                =                      0            ⁢                          (                              m                ≠                0                            )                                                          (        9        )            
In the same way, the following Expression (10) holds with regard to t=1, 2, . . . , T.Expression (10)                                                         β              t                        ⁡                          (              m              )                                =                                                    ∑                                                      m                    ′                                    =                  0                                                  M                  -                  1                                            ⁢                                                                    β                                          t                      +                      1                                                        ⁡                                      (                                          m                      ′                                        )                                                  ⁢                                                      γ                                          t                      +                      1                                                        ⁡                                      (                                          m                      ,                                              m                        ′                                                              )                                                  ⁢                                                                   ⁢                ⁢                                                                   ⁢                                                      β                    T                                    ⁡                                      (                    0                    )                                                                        =            1                          ,                                            β              T                        ⁡                          (              m              )                                =                      0            ⁢                          (                              m                ≠                0                            )                                                          (        10        )            
Moreover, the following Expression (11) holds with regard to λt.Expression (11)                                           γ            t                    ⁡                      (                                          m                ′                            ,              m                        )                          =                  {                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 ⁢                                                                                                      P                      t                                        (                                          m                      ⁢                                                                                                                              m                            ′                                                    )                                                ·                        Pr                                            ⁢                                              {                                                                              y                            t                                                    |                                                      x                            ⁡                                                          (                                                                                                m                                  ′                                                                ,                                m                                                            )                                                                                                      }                                                                                                                                                                                                                             ⁢                                          =                                              Pr                        ⁢                                                                              {                                                                                          i                                t                                                            =                                                              i                                ⁡                                                                  (                                                                                                            m                                      ′                                                                        ,                                    m                                                                    )                                                                                                                      }                                                    ·                          Pr                                                ⁢                                                  {                                                                                    y                              t                                                        |                                                          x                              ⁡                                                              (                                                                                                      m                                    ′                                                                    ,                                  m                                                                )                                                                                                              }                                                                                                                                                                                                                                                              :                                          case                      ⁢                                                                                           ⁢                      wherein                      ⁢                                                                                           ⁢                      transition                      ⁢                                                                                           ⁢                      is                      ⁢                                                                                           ⁢                      made                                                                                                                                                                                                       ⁢                                          from                      ⁢                                                                                           ⁢                                              m                        ′                                            ⁢                                                                                           ⁢                      to                      ⁢                                                                                           ⁢                      m                      ⁢                                                                                           ⁢                      with                      ⁢                                                                                           ⁢                      input                      ⁢                                                                                           ⁢                      i                                                                                                                    0                                                                                                                                                                        :                                          case                      ⁢                                                                                           ⁢                      wherein                      ⁢                                                                                           ⁢                      transition                      ⁢                                                                                           ⁢                      is                      ⁢                                                                                           ⁢                      not                      ⁢                                                                                           ⁢                      made                                                                                                                                                                                                       ⁢                                          from                      ⁢                                                                                           ⁢                                              m                        ′                                            ⁢                                                                                           ⁢                      to                      ⁢                                                                                           ⁢                      m                      ⁢                                                                                           ⁢                      with                      ⁢                                                                                           ⁢                      input                      ⁢                                                                                           ⁢                      i                                                                                                                              (        11        )            
Accordingly, in the event of performing soft-output decoding by applying the BCJR algorithm, the decoding apparatus 203 obtains the soft-output λtj by performing a series of processes shown in FIG. 22 based upon these relationships.
First of all, as shown in the drawing, in Step S201, the decoding apparatus 203 calculates the probabilities αt(m) and λt(m′, m) using the above Expression (9) and the above Expression (11) every time yt is received.
Next, in Step S202, the decoding apparatus 203 calculates the probability βt(m) with regard to each state m in all times t using the above Expression (10) following receiving of the entire system Y1T.
In Step S203, the decoding apparatus 203 then substitutes the probabilities αt, βt, and γt, which are calculated in Step S201 and Step S202, into the above Expression (8) so as to calculate the soft-output λt at each time t.
The decoding apparatus 203 can perform soft-output decoding wherein the BCJR algorithm is applied, by performing a series of processes described above.
Now, with the BCJR algorithm, computation has to be performed with the probabilities being held as the values which are to be handled, and there are difficulties wherein the amount of computations is great due to multiplication being included. As techniques for reducing the amount of computations, the Max-Log-MAP algorithm and Log-MAP algorithm (which will be referred to as the “Max-Log-BCJR algorithm” and “Log-BCJR algorithm” hereafter) have been described in “Robertson, Villebrun and Hoeher, ‘A comparison of optimal and sub-optimal MAP decoding algorithms operating in the domain’, IEEE Int. Conf. on Communications, pp. 1009-1013, June 1995”.
First of all, the Max-Log-BCJR algorithm will be described. The Max-Log-BCJR algorithm is a function consisting of writing the probabilities αt, βt, and γt, and the soft-output λt, as a logarithm using the natural logarithm, rewriting the multiplication with regard to the probabilities as the addition in the logarithm as shown in the following Expression (12), and also approximating the addition regarding the probabilities with the maximum value computation in the logarithm as shown in the following Expression (13). Note that max(x, y) represents the function wherein the greater value of x or y is selected.
Expression (12)log(ex·ey)=x+y  (12)Expression (13)log(ex+ey)≈max(x,y)  (13)
Here, to simplify description, the natural logarithm will be abbreviated as I, and the natural logarithmic values of αt, βt, γt, and λt, will be represented by Iαt, Iβt, Iγt, and Iλt, respectively, as shown in the following Expression (14). Note that sgn shown in the following Expression (14) is the constant indicating a sign for specifying positive or negative, i.e., either of “+1” or “−1”.Expression (14)                     {                                                                              I                  ⁢                                                                           ⁢                                                            α                      t                                        ⁡                                          (                      m                      )                                                                      =                                                      sgn                    ·                    log                                    ⁢                                                                           ⁢                                      (                                                                  α                        t                                            ⁡                                              (                        m                        )                                                              )                                                                                                                                            I                  ⁢                                                                           ⁢                                                            β                      t                                        ⁡                                          (                      m                      )                                                                      =                                                      sgn                    ·                    log                                    ⁢                                                                           ⁢                                      (                                                                  β                        t                                            ⁡                                              (                        m                        )                                                              )                                                                                                                                            I                  ⁢                                                                           ⁢                                                            γ                      t                                        ⁡                                          (                      m                      )                                                                      =                                                      sgn                    ·                    log                                    ⁢                                                                           ⁢                                      (                                                                  γ                        t                                            ⁡                                              (                        m                        )                                                              )                                                                                                                                                                I                    ⁢                                                                                   ⁢                                          λ                      t                                                        =                                                            sgn                      ·                      log                                        ⁢                                                                                   ⁢                                          λ                      t                                                                      ⁢                                                                                                                           (        14        )            
The main reason that the constant sgn is given as described above, is that the calculated logarithmic likelihood (log likelihood) Iαt, Iβt, and Iγt, generally have negative values due to the probabilities αt, βt, and γt, having values between 0 and 1.
For example, while in the event that the decoding apparatus 203 is configured as software, both positive values and negative values can be processed, and accordingly the constant sgn may be “+1” or “−1”, in the event that the decoding apparatus 203 is configured as hardware, it is desirable that the calculated positive/negative specification symbol of the negative value is reversed so as to handle as a positive value in order to reduce the number of bits.
That is to say, in the event that the decoding apparatus 203 is configured as a system which handles only the negative values as log likelihood, the constant sgn is “+1”, in the event that the decoding apparatus 203 is configured as a system which handles only the positive values as log likelihood, the constant sgn is “−1”. Description will be made with regard to the algorithm wherein the constant sgn described above is taken into consideration.
In the Max-Log-BCJR algorithm, the log likelihoods Iαt, Iβt, and Iγt, are approximated as shown in the following Expression (15) through the following Expression (17), respectively. Here, in the event that the constant sgn is “+1”, msgn(x, y) shown in the following Expression (15) and the following Expression (16) represents the function max(x, y) wherein the greater value of x or y is selected, and in the event that the constant sgn is “−1”, represents the function min(x, y) wherein the smaller value of x or y is selected. The function msgn in the state m′ in the right side in the following Expression (15) is obtained in the state m′ in which the transition to the state m occurs, and the function msgn in the state m′ in the right side in following Expression (16) is obtained in the state m′ in which the transition from the state m occurs.Expression (15)                               I          ⁢                                           ⁢                                    α              t                        ⁡                          (              m              )                                      ≈                  m          ⁢                                           ⁢                                    sgn                              m                ′                                      ⁡                          (                                                I                  ⁢                                                                           ⁢                                                            α                                              t                        -                        1                                                              ⁡                                          (                                              m                        ′                                            )                                                                      +                                  I                  ⁢                                                                           ⁢                                                            γ                      t                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                                                  )                                                          (        15        )            Expression (16)                               I          ⁢                                           ⁢                                    β              t                        ⁡                          (              m              )                                      ≈                  m          ⁢                                           ⁢                                    sgn                              m                ′                                      ⁡                          (                                                I                  ⁢                                                                           ⁢                                                            β                                              t                        +                        1                                                              ⁡                                          (                                              m                        ′                                            )                                                                      +                                  I                  ⁢                                                                           ⁢                                                            γ                                              t                        +                        1                                                              ⁡                                          (                                              m                        ,                                                  m                          ′                                                                    )                                                                                  )                                                          (        16        )            Expression (17)                               I          ⁢                                           ⁢                                    γ              t                        ⁡                          (                                                m                  ′                                ,                m                            )                                      =                  sgn          ·                      (                                          log                ⁡                                  (                                      Pr                    ⁢                                          {                                                                        i                          t                                                =                                                  i                          ⁡                                                      (                                                                                          m                                ′                                                            ,                              m                                                        )                                                                                              }                                                        )                                            +                              log                ⁡                                  (                                      Pr                    ⁢                                          {                                                                        y                          t                                                |                                                  x                          ⁡                                                      (                                                                                          m                                ′                                                            ,                              m                                                        )                                                                                              }                                                        )                                                      )                                              (        17        )            
In the same way, in the Max-Log-BCJR algorithm, the logarithmic soft-output Iλt is also approximated as shown in the following Expression (18). Here, in the event that the input is “1”, the function msgn in the first argument in the right side in the following Expression (18) is obtained in the state m′ in which the transition to the state m occurs, and in the event that the input is “0”, the function msgn in the second argument is obtained in the state m′ in which the transition to the state m occurs.Expression (18)                                                                         I                ⁢                                                                   ⁢                                  λ                  tj                                            ≈                            ⁢                                                                                          m                      ⁢                                                                                           ⁢                      sgn                                                                                                                m                          ′                                                ,                        m                                                                                                                          i                            j                                                    ⁡                                                      (                                                                                          m                                ′                                                            ,                              m                                                        )                                                                          =                        1                                                                              ⁢                                      (                                                                  I                        ⁢                                                                                                   ⁢                                                                              α                                                          t                              -                              1                                                                                ⁡                                                      (                                                          m                              ′                                                        )                                                                                              +                                              I                        ⁢                                                                                                   ⁢                                                                              γ                            t                                                    ⁡                                                      (                                                                                          m                                ′                                                            ,                              m                                                        )                                                                                              +                                              I                        ⁢                                                                                                   ⁢                                                                              β                            t                                                    ⁡                                                      (                            m                            )                                                                                                                )                                                  -                                                                                                      ⁢                                                                    m                    ⁢                                                                                   ⁢                    sgn                                                                                                      m                        ′                                            ,                      m                                                                                                                i                          j                                                ⁡                                                  (                                                                                    m                              ′                                                        ,                            m                                                    )                                                                    =                      0                                                                      ⁢                                  (                                                            I                      ⁢                                                                                           ⁢                                                                        α                                                      t                            -                            1                                                                          ⁡                                                  (                                                      m                            ′                                                    )                                                                                      +                                          I                      ⁢                                                                                           ⁢                                                                        γ                          t                                                ⁡                                                  (                                                                                    m                              ′                                                        ,                            m                                                    )                                                                                      +                                          I                      ⁢                                                                                           ⁢                                                                        β                          t                                                ⁡                                                  (                          m                          )                                                                                                      )                                                                                        (        18        )            
Accordingly, in the event that soft-output decoding is performed by applying the Max-Log-BCJR algorithm, the decoding apparatus 203 obtains the soft-output λt by following a series of processes shown in FIG. 23 based upon these relationships described above.
First of all, in Step S211, the decoding apparatus 203 calculates the logarithmic likelihoods Iαt(m), Iβt(m), and Iγt(m′, m), using the above Expression (15) and the above Expression (17) each time yt is received, as shown in the drawing.
Next, In Step S212, the decoding apparatus 203 calculates the logarithmic likelihood Iβt(m) for each state m at all the times t, using the above Expression (16) following receiving of the entire system YIT.
In Step S213, the decoding apparatus 203 then calculates the logarithmic soft-output Iλt at each time t by substituting the logarithmic likelihoods Iαt, Iβt, and Iγt, which have been calculated in Step S211 and Step S212, into the above Expression (18).
The decoding apparatus 203 can perform soft-output encoding to which the Max-log-BCJR algorithm is applied, by following such a series of processes.
As described above, the Max-log-BCJR algorithm does not include multiplication, and accordingly the amount of computations can be reduced as compared with the BCJR algorithm.
The Log-BCJR algorithm will now be described. The Log-BCJR algorithm has been developed so as to further improve precision of approximation of the Max-Log-BCJR algorithm. Specifically, the Log-BCJR algorithm is modified from the Max-Log-BCRJ algorithm, by adding the compensation argument to the addition regarding the probabilities shown in the above Expression (13), as shown in the following Expression (19), so as to obtain a precise logarithmic value of addition. Here, the above-described compensation will be referred to as the log-sum compensation.Expression (19)                               log          ⁡                      (                                          ⅇ                x                            +                              ⅇ                y                                      )                          =                              max            ⁡                          (                              x                ,                y                            )                                +                      log            ⁡                          (                              1                +                                  ⅇ                                      -                                                                                        x                        -                        y                                                                                                                              )                                                          (        19        )            
Here, the computation shown in the left side in the above Expression (19) will be referred to as the log-sum computation, and the operator of the log-sum computation will be represented as “#” (which is represented as “E” in the following description), for convenience, following the rules described in “S. S. Pietrobon, ‘Implementation and performance of a turbo/MAP decoder’, Int. J. Satellite Commun., vol. 16, pp. 23-46, January-February 1998.”
Expression (20)x#y=log(ex+ey)  (20)
Note that the above-described constant sgn is assumed to be “+1” in the above Expression (19) and the above Expression (20). In the event that the constant sgn is “−1”, the following Expression (21) and the following Expression (22) holds, corresponding to the above Expression (19) and the above Expression (20), respectively.
Expression (21)−log(e−x+e−y)=min(x,y)−log(1+e−|x-y|)  (21)Expression (22) x#y=−log(e−x+e−y)  (22)
Moreover, the operator of accumulated addition of the log-sum computation will be represented as “#Σ” (which is represented as “E” in the description) as shown in the following Expression (23).Expression (23)                               #          ⁢                                    ∑                              i                =                0                                            M                -                1                                      ⁢                                                   ⁢                          x              i                                      =                  (                                    (                                                ⋯                  ⁡                                      (                                                                  (                                                                              x                            0                                                    ⁢                          #                          ⁢                                                      x                            1                                                                          )                                            ⁢                      #                      ⁢                                              x                        2                                                              )                                                  ⁢                                                                   ⁢                ⋯                            )                        ⁢            #            ⁢                          x                              M                -                1                                              )                                    (        23        )            
Using these operators, the logarithmic likelihoods Iαt and Iβt and the logarithm soft-output Iλ can be represented as shown in the following Expressions (24) through (26), respectively. Note that the logarithmic likelihood Iγt is represented as in the above Expression (17), so description thereof will be omitted. Expression (24)                               I          ⁢                                           ⁢                                    α              i                        ⁡                          (              m              )                                      =                  #          ⁢                                    ∑                                                m                  ′                                =                0                                            M                -                1                                      ⁢                          (                                                I                  ⁢                                                                           ⁢                                                            α                                              t                        -                        1                                                              ⁡                                          (                                              m                        ′                                            )                                                                      +                                  I                  ⁢                                                                           ⁢                                                            γ                      t                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                                                  )                                                          (        24        )            Expression (25)                               I          ⁢                                           ⁢                                    β              t                        ⁡                          (              m              )                                      =                  #          ⁢                                    ∑                                                m                  ′                                =                0                                            M                -                1                                      ⁢                          (                                                I                  ⁢                                                                           ⁢                                                            β                                              t                        +                        1                                                              ⁡                                          (                                              m                        ′                                            )                                                                      +                                  I                  ⁢                                                                           ⁢                                                            γ                                              i                        +                        1                                                              ⁡                                          (                                              m                        ,                                                  m                          ′                                                                    )                                                                                  )                                                          (        25        )            Expression (26)                               I          ⁢                                           ⁢                      λ            tj                          =                                                            #                ⁢                Σ                                                                                  m                    ′                                    ,                  m                                                                                            i                      j                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                        =                  1                                                      ⁢                          (                                                I                  ⁢                                                                           ⁢                                                            α                                              i                        -                        1                                                              ⁡                                          (                                              m                        ′                                            )                                                                      +                                  I                  ⁢                                                                           ⁢                                                            γ                      t                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                                      +                                  I                  ⁢                                                                           ⁢                                                            β                      t                                        ⁡                                          (                      m                      )                                                                                  )                                -                                                    #                ⁢                Σ                                                                                  m                    ′                                    ,                  m                                                                                            i                      j                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                        =                  0                                                      ⁢                          (                                                I                  ⁢                                                                           ⁢                                                            α                                              i                        -                        1                                                              ⁡                                          (                                              m                        ′                                            )                                                                      +                                  I                  ⁢                                                                           ⁢                                                            γ                      t                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                                      +                                  I                  ⁢                                                                           ⁢                                                            β                      t                                        ⁡                                          (                      m                      )                                                                                  )                                                          (        26        )            
Note that the accumulated addition of the log-sum computation in the state m′ in the right side in the above Expression (24) is obtained in the state m′ in which the transition to the state m occurs, and the accumulated addition of the log-sum computation in the state m′ in the right side in the above Expression (25) is obtained in the state m′ in which the transition from the state m occurs. Also, in the above Expression (26), in the event that the input is “1”, the accumulated addition of the log-sum computation of the first argument in the right side is obtained in the state m′ in which the transition to the state m occurs, and in the event that the input is “0”, the accumulated addition of the log-sum computation of the second argument is obtained in the state m′ in which the transition to the state m occurs.
Accordingly, in the event that soft-output decoding is performed by applying the Log-BCRJ algorithm, the decoding apparatus 203 can obtain the soft-output λt by following a series of processes as shown in the above-described FIG. 23, based upon these relationships.
First of all, in Step S211, the decoding apparatus 203 calculates the logarithmic likelihoods Iαt(m) and Iλt(m′, m), each time yt is received, using the above Expression (24) and the above Expression (17), as shown in the drawing.
Next, in Step S212, the decoding apparatus 203 calculates Iβt(m) for each state m at all the times t, following receiving of the entire system Y1T, using the above Expression (25).
In Step S213, the decoding apparatus 203 then calculates the logarithmic soft-output Iλt at each time t by substituting the logarithmic likelihoods Iαt, Iβt, and Iγt, which have been calculated in Step S211 and Step S212, into the above Expression (26).
The decoding apparatus 203 can perform soft-output decoding, which the Log-BCJR algorithm is applied, by following a series of processes described above. Note that in the above Expression (19) and the above Expression (21), the compensation argument shown in the second argument in the right side is represented by a one-dimensional function with regard to the variable |x−y|, and accordingly the decoding apparatus 203 can perform precise probability calculation by storing these values as a table in the ROM (Read Only Memory) or the like, which is not shown in the drawings.
While the amount of computations in the Log-BCJR algorithm increases as compared with that in the Max-Log-BCJR algorithm, multiplication is not included, and the output is the logarithmic value of the soft-output except for quantization margin of error.
While the BCJR algorithm, the Max-Log-BCJR algorithm, or the Log-BCJR algorithm, are algorithms which enable decoding of trellis codes such as convolutional codes or the like, the algorithm can be applied to decoding of codes generated by concatenating multiple component encoders wherein the component codes are the trellis codes, via interleavers. That is to say, the BCJR algorithm, the Max-Log-BCJR algorithm, or the Log-BCJR algorithm, can be applied to decoding of the PCCC or SCCC, described above, or turbo trellis encoded modulation (which will be referred to as “TTCM” hereafter) or serial concatenated trellis encoded modulation (which will be referred to as SCTCM hereafter), wherein the above-described PCCC or SCCC is applied to multi-value modulation so as to integrate and take into consideration the decoding performance of the positioning of the signal point and error correction codes.
The decoding apparatus for decoding the PCCC, SCCC, TTCM, or SCTCM, concatenates multiple decoders for performing Maximum A Posteriori probability (MAP) decoding based upon the BCJR algorithm, the Max-Log-BCJR algorithm, or the Log-BCJR algorithm, via interleavers, so as to perform so-called repeated decoding.
Here, a storage device such as RAM (Random Access Memory) or the like is used as an interleaver, and performs interleaving by writing data in a certain order and reading the data in a different order from the writing order. In this case, there is the need to use a storage device with capacity for storage of data twice the interleaving length as an interleaver.
Specifically, an example wherein data of which one frame corresponds to the interleaving length for ten time slots is interleaved using two banks of RAM of which number of words corresponds to ten time slots is shown in FIGS. 24 through 29. Here, for convenience, one of the two banks, shown at the upper side in the drawings, is referred to as a bank A, and the other, shown at the lower side in the drawings, is referred to as a bank B. Also, addresses 0, 1, 2, . . . , 9, are assigned to each bank of RAM, from the left side in the drawing, respectively. Moreover, writing of data is denoted by W and reading of data is denoted by R in the drawings.
First of all, the interleaver writes the first frame of data in the bank A RAM.
That is to say, as shown in FIG. 24, the interleaver writes the data DD0 in the storage area at the address 0 in the bank A RAM in the 0th time slot. Next, the interleaver writes the data DD1 in the storage area at the address 1 in the bank A RAM in the 1st time slot, writes the data DD2 in the storage area at the address 2 in the bank A RAM in the 2nd time slot, and writes the data DD3 in the storage area at the address 3 in the bank A RAM in the 3rd time slot. In the same way, the interleaver writes the data in the storage area at each address in the bank A RAM in each time slot, and writes the data DD9 in the storage area at the address 9 in the bank A RAM in the ninth time slot.
As described above, the interleaver writes the first frame of data in the bank A RAM in the order of DD0, DD1, DD2, DD3, DD4, DD5, DD6, DD7, DD8, and DD9.
Next, the interleaver reads out the first frame of data, which has been written in the bank A RAM, in a different order from the writing order, and also writes the second frame of data in the bank B RAM.
That is to say, as shown in FIG. 25, in the 10th time slot, the interleaver reads out the data DD2 from the storage area at the address 2 in the bank A RAM, i.e., the storage area in which the data DD2 has been written in the second time slot, and also writes the data DD10 in the storage area at the address 0 in the bank B RAM. Next, in the 11th time slot, the interleaver reads out the data DD9 from the storage area at the address 9 in the bank A RAM, i.e., the storage area in which the data DD9 has been written in the 9th time slot, and also writes the data DD11 in the storage area at the address 1 in the bank B RAM. Next, in the 12th time slot, the interleaver reads out the data DD0 from the storage area at the address 0 in the bank A RAM, i.e., the storage area in which the data DD0 has been written in the 0th time slot, and also writes the data DD12 in the storage area at the address 2 in the bank B RAM. Next, in the 13th time slot, the interleaver reads out the data DD5 from the storage area at the address 5 in the bank A RAM, i.e., the storage area in which the data DD5 has been written in the 5th time slot, and also writes the data DD13 in the storage area at the address 3 in the bank B RAM. Next, in the 14th time slot, the interleaver reads out the data DD4 from the storage area at the address 4 in the bank A RAM, i.e., the storage area in which the data DD4 has been written in the 4th time slot, and also writes the data DD14 in the storage area at the address 4 in the bank B RAM.
Moreover, as shown in FIG. 26, in the 15th time slot, the interleaver reads out the data DD3 from the storage area at the address 3 in the bank A RAM, i.e., the storage area in which the data DD3 has been written in the 3rd time slot, and also writes the data DD15 in the storage area at the address 5 in the bank B RAM. Next, in the 16th time slot, the interleaver reads out the data DD8 from the storage area at the address 8 in the bank A RAM, i.e., the storage area in which the data DD8 has been written in the 8th time slot, and also writes the data DD16 in the storage area at the address 6 in the bank B RAM. Next, in the 17th time slot, the interleaver reads out the data DD7 from the storage area at the address 7 in the bank A RAM, i.e., the storage area in which the data DD7 has been written in the 7th time slot, and also writes the data DD17 in the storage area at the address 7 in the bank B RAM. Next, in the 18th time slot, the interleaver reads out the data DD6 from the storage area at the address 6 in the bank A RAM, i.e., the storage area in which the data DD6 has been written in the 6th time slot, and also writes the data DD18 in the storage area at the address 8 in the bank B RAM. In the 19th time slot, the interleaver then reads out the data DD1 from the storage area at the address 1 in the bank A RAM, i.e., the storage area in which the data DD1 has been written in the 1st time slot, and also writes the data DD19 in the storage area at the address 9 in the bank B RAM.
As described above, the interleaver reads out all of the first frame of the data which has been written in the bank A RAM in the order of DD0, DD1, DD2, DD3, DD4, DD5, DD6, DD7, DD8, and DD9, in a different order from the writing order, i.e., in the order of DD2, DD9, DD0, DD5, DD4, DD3, DD8, DD7, DD6, and DD1, and also writes the second frame of data in the bank B RAM in the order of DD10, DD11, DD12, DD13, DD14, DD15, DD16, DD17, DD18, and DD19.
Next, the interleaver reads out the second frame of data which has been written in the bank B RAM in a different order from the writing order, and also writes the third frame of data in the bank A RAM.
That is to say, as shown in FIG. 27, in the 20th time slot, the interleaver reads out the data DD12 from the storage area at the address 2 in the bank B RAM, i.e., the storage area in which the data DD12 has been written in the 12th time slot, and also writes the data DD20 in the storage area at the address 0 in the bank A RAM, i.e., the storage area from which the data DD0 has been read out in the 12th time slot and now is empty. Next, in the 21st time slot, the interleaver reads out the data DD19 from the storage area at the address 9 in the bank B RAM, i.e., the storage area in which the data DD19 has been written in the 19th time slot, and also writes the data DD21 in the storage area at the address 1 in the bank A RAM, i.e., the storage area from which the data DD1 has been read out in the 19th time slot and now is empty. Next, in the 22nd time slot, the interleaver reads out the data DD10 from the storage area at the address 0 in the bank B RAM, i.e., the storage area in which the data DD10 has been written in the 10th time slot, and also writes the data DD22 in the storage area at the address 2 in the bank A RAM, i.e., the storage area from which the data DD2 has been read out in the 10th time slot and now is empty. Next, in the 23rd time slot, the interleaver reads out the data DD15 from the storage area at the address 5 in the bank B RAM, i.e., the storage area in which the data DD15 has been written in the 15th time slot, and also writes the data DD23 in the storage area at the address 3 in the bank A RAM, i.e., the storage area from which the data DD3 has been read out in the 15th time slot and now is empty. Next, in the 24th time slot, the interleaver reads out the data DD14 from the storage area at the address 4 in the bank B RAM, i.e., the storage area in which the data DD14 has been written in the 14th time slot, and also writes the data DD24 in the storage area at the address 4 in the bank A RAM, i.e., the storage area from which the data DD4 has been read out in the 14th time slot and now is empty.
Moreover, as shown in FIG. 28, in the 25th time slot, the interleaver reads out the data DD13 from the storage area at the address 3 in the bank B RAM, i.e., the storage area in which the data DD13 has been written in the 13th time slot, and also writes the data DD25 in the storage area at the address 5 in the bank A RAM, i.e., the storage area from which the data DD5 has been read out in the 13th time slot and now is empty. Next, in the 26th time slot, the interleaver reads out the data DD18 from the storage area at the address 8 in the bank B RAM, i.e., the-storage area in which the data DD18 has been written in the 18th time slot, and also writes the data DD26 in the storage area at the address 6 in the bank A RAM, i.e., the storage area from which the data DD6 has been read out in the 18th time slot and now is empty. Next, in the 27th time slot, the interleaver reads out the data DD17 from the storage area at the address 7 in the bank B RAM, i.e., the storage area in which the data DD17 has been written in the 17th time slot, and also writes the data DD27 in the storage area at the address 7 in the bank A RAM, i.e., the storage area from which the data DD7 has been read out in the 17th time slot and now is empty. Next, in the 28th time slot, the interleaver reads out the data DD16 from the storage area at the address 6 in the bank B RAM, i.e., the storage area in which the data DD16 has been written in the 16th time slot, and also writes the data DD28 in the storage area at the address 8 in the bank A RAM, i.e., the storage area from which the data DD8 has been read out in the 16th time slot and now is empty. In the 29th time slot, the interleaver reads out the data DD11 from the storage area at the address 1 in the bank B RAM, i.e., the storage area in which the data DD11 has been written in the 11th time slot, and also writes the data DD29 in the storage area at the address 9 in the bank A RAM, i.e., the storage area from which the data DD9 has been read out in the 11th time slot and now is empty.
As described above, the interleaver reads out all the second frame of the data which has been written in the order of DD10, DD11, DD12, DD13, DD14, DD15, DD16, DD17, DD18, and DD19, in the bank B RAM, in a different order from the writing order, i.e., in the order of DD12, DD19, DD10, DD15, DD14, DD13, DD18, DD17, DD16, and DD11, and also writes the third frame of data in the bank A RAM in the order of DD20, DD21, DD22, DD23, DD24, DD25, DD26, DD27, DD28, and DD29.
In the same way, the interleaver reads out the third frame of data which has been written in the bank A RAM in a different order from the writing order, and also writes the fourth frame of data in the bank B RAM.
That is to say, as shown in FIG. 29, in the 30th time slot, the interleaver reads out the data DD22 from the storage area at the address 2 in the bank A RAM, i.e., the storage area in which the data DD22 has been written in the 22nd time slot, and also writes the data DD30 in the storage area at the address 0 in the bank B RAM, i.e., the storage area from which the data DD10 has been read out in the 22nd time slot and now is empty. Next, in the 31st time slot, the interleaver reads out the data DD29 from the storage area at the address 9 in the bank A RAM, i.e., the storage area in which the data DD29 has been written in the 29th time slot, and also writes the data DD31 in the storage area at the address 1 in the bank B RAM, i.e., the storage area from which the data DD11 has been read out in the 29th time slot and now is empty. Next, in the 32nd time slot, the interleaver reads out the data DD20 from the storage area at the address 0 in the bank A RAM, i.e., the storage area in which the data DD20 has been written in the 20th time slot, and also writes the data DD32 in the storage area at the address 2 in the bank B RAM, i.e., the storage area from which the data DD12 has been read out in the 20th time slot and now is empty. In the 33rd time slot, the interleaver then reads out the data DD25 from the storage area at the address 5 in the bank A RAM, i.e., the storage area in which the data DD25 has been written in the 25th time slot, and also writes the data DD33 in the storage area at the address 3 in the bank B RAM, i.e., the storage area from which the data DD13 has been read out in the 25th time slot and now is empty.
As described above, the interleaver reads out all the third frame of the data which has been written in the bank A RAM in the order of DD20, DD21, DD22, DD23, DD24, DD25, DD26, DD27, DD28, and DD29, in a different order from the writing order, i.e., DD22, DD29, DD20, DD25, . . . , and also writes the fourth frame of the data in the bank B RAM in the order of DD30, DD31, DD32, DD33, . . . .
As described above, the interleaver can perform interleaving wherein writing of data and reading of data can be continuously performed by using two banks of RAM having the same capacity as the interleaving length, i.e., RAM having capacity twice the interleaving length, and switching between the operations wherein data is written in one of the banks in an order and data is read out from the other bank in a different order from the writing order, between the two banks. At this time, as described above, an arrangement may be made wherein the interleaver writes data in the RAM in a sequential manner, as well as reading data which has been written in the RAM following a reading order which is generated by a predetermined circuit, or is read out from a predetermined storage medium in which an interleaving pattern has been stored as the reading order. Conversely, an arrangement may also be made wherein the interleaver writes data in the RAM following a writing order which is generated by a predetermined circuit, or is read out from a predetermined storage medium in which an interleaving pattern has been stored as the writing order, as well as reading data written in the RAM in a sequential manner.
Now, it is known that in a case of applying an interleaver to a decoding apparatus for decoding PCCC, SCCC, TTCM, or SCTCM, the longer the length of the interleaving length is, the more the code performance is improved.
However, a storage device having the capacity twice the interleaver length for storing of data has been used for an interleaver for the reason that operations are necessitated wherein the data which is to be interleaved is temporarily written in a storage device of the interleaving length and also the data which has been written in the storage device is read out, due to the writing order for the data being different from the reading order for the data, as described above. Accordingly, in a case of applying the above-described interleaver to the decoding apparatus, in the event that the interleaving length of the interleaver is increased, the size of the storage device in the decoding apparatus increases, causing the problem in that the circuit size of the decoding apparatus also increases.
Also, the interleaver is an indispensable component in encoding apparatuses for performing encoding by PCCC, SCCC, TTCM, or SCTCM, and accordingly, in a case of applying the interleaver to the encoding apparatus, in the event that the interleaving length increases, the size of the storage device in the encoding apparatus increases, causing the problem in that the circuit scale of the decoding apparatus increases.